package 滑动窗口And双指针;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/18 15:12
 */
public class 数组求和的变种问题 {
    /*
    注意这个题 还可以 使用
    窗口 进行 一个优化,
    记着有这个 优化的方式
    但是递归的方式 会有些 小小的 变化
    ** 多重背包 的方式 **
     */


    /*
    这个题就比较的熟悉了
    而该题的 问法 就不一样了
    求得 是 使用 数组中元素 个数 最少得 个数
    nums[] , aim
    nums 中  有重复元素
     */

    public static int rescursionBinanryTree(int index,int rest,int []nums,int len){
        // rest == 0 才是basecase 的首要判断点
        if(rest == 0)
            return 0;
        if(index == len)
            // 返回一个 对 结果 没有影响的数就可以了,因为 最终的 结果一定是 <= len ,没必要返回 int 的最大子相关的
            return len;
        /*
        习惯性的 把这里的 ans 赋值 为 0, 如果这里 把 ans1 赋值 为 0 就会出现问题
        比如 ,如果 if rest - nums[index] 不满足的话 那么 ans1 就是 0 ,而最后 又取 min 所以 出现问题
         */
        int ans1 = len;
        if(rest - nums[index] >= 0)
            ans1 = rescursionBinanryTree(index + 1,rest - nums[index],nums,len) + 1;
        int ans = rescursionBinanryTree(index + 1,rest ,nums,len);
        return Math.min(ans1,ans);
    }
    public static int recursionMultiTree(int index,int rest,int nums[],int len){
        if(rest == 0)
            return 0;
        int ans = len;
        for(int i = index;i < len;i++){
            if(rest - nums[i] >= 0)
            ans = Math.min(ans,recursionMultiTree(i + 1,rest - nums[i],nums,len) + 1);
        }
        return ans;
    }


    public static void main(String[] args) {
        int nums [] = {2,4,5,3,2,6,5};
        int aim = 15;
        System.out.println(recursionMultiTree(0,aim,nums,nums.length));
        System.out.println(rescursionBinanryTree(0,aim,nums, nums.length));
    }
}
